#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int MAX_N = 500;
const int MAX_E = 10000;
const int INF = 20000000;
const int MAX_LEV = 5000000;
int gmap[MAX_N][MAX_N];
int ori[MAX_N];
int que[MAX_N];
bool used[MAX_N];
int path[MAX_N];

int es,ns;//edge size ,node size
int src,dest;
void init();
int lev[MAX_N];
void mklev();
void showlev();
void dfs(int);
int main()
{
    freopen("dat.in","r",stdin);
    freopen("dat.out","w",stdout);
    while (scanf("%d%d",&es,&ns)!=EOF){
        init();
        memset(path,0,sizeof(path));
        while (true){
            mklev();
           // showlev();
            if (lev[dest]==MAX_LEV)
                break;
            dfs(src);
        }
        int ans=0;
        int i=0;
        for (i=1;i<=ns;i++){
            ans+=(gmap[i][src]-ori[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}
void init(){
    memset(gmap,0,sizeof(gmap));
    int i;
    int fr,to;
    int cap;
    for (i=0;i<es;i++){
        scanf("%d%d%d",&fr,&to,&cap);
        gmap[fr][to]+=cap;
    }
    src=1;
    dest=ns;
    for (i=1;i<=ns;i++)
        ori[i]=gmap[i][src];
}


void dfs(int node){
    if (gmap[path[node]][node]==0 && node!=src)
       return ;
    if (node==dest){
        int cur = node;
        int up = path[cur];
        int min =INF;
        while (cur!=src){
            if (gmap[up][cur]<min)
                min=gmap[up][cur];
            cur = up;
            up=path[cur];
        }
        cur=node;
        up =path[cur];
        while(cur!=src){
            gmap[up][cur]-=min;
            gmap[cur][up]+=min;
            cur=up;
            up=path[cur];
        }
        return ;
    }
    int i;
    for (i=1;i<=ns;i++){
        if (node==src ||gmap[path[node]][node]>0){
            if (gmap[node][i]>0 && lev[i]==lev[node]+1){
                path[i]=node;
                dfs(i);
            }
        }
    }
}
void mklev(){
    //init
    int i;
    for (i=1;i<=ns;i++)
        lev[i]=MAX_LEV;
    int head=0,tail=0;
    lev[src]=1;
    que[0]=src;
    tail=1;
    memset(used,false,sizeof(used));
    used[src]=true;
    while (head<tail && tail <MAX_N){
        int node = que[head];
        head++;
        if (node==dest){
            break;
        }
        for (i=1;i<=ns;i++)
        {
            if (!used[i] && gmap[node][i]>0 ){
                used[i]=true;
                que[tail]=i;
                tail++;
                lev[i]=lev[node]+1;
            }
        }
    }
}
void showlev(){

    cout<<"show lev:"<<endl;
    int i;
    for (i=1;i<=ns;i++){
        printf("lev[%d] = %d\n",i,lev[i]);
    }

}
